package com.xsherl.leetcode.solution;

import cn.hutool.core.lang.Assert;
import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.*;

public class Permutations2 {

    boolean[] via;

    /**
     * DFS + 剪枝
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        via = new boolean[nums.length];
        Arrays.sort(nums);
        permuteUnique(nums, new LinkedList<>(), res);
        return res;
    }

    private void permuteUnique( int[] nums, LinkedList<Integer> list, List<List<Integer>> res){
        if (list.size() == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; ++i){
            // 如果正在路径中 或者 前一个数和当前值相同并且也在路径中，就跳过
            if (via[i] || (i > 0 && nums[i] == nums[i - 1] && via[i - 1])){
                continue;
            }
            list.push(nums[i]);
            via[i] = true;
            permuteUnique( nums, list, res);
            via[i] = false;
            list.pop();
        }
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1};
        List<List<Integer>> permute = new Permutations2().permuteUnique(nums);
        PrintUtils.println(permute);
        List<List<Integer>> integers = ArrayUtils.parse("" +
                "[[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]" +
                "");
        Assert.isTrue(ArrayUtils.allMatch(permute, integers));
    }
}
